//https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=23259&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想:1.动态规划f(n)=f(n-1)+cur[i]或者cur[i]；
//2.滑动窗口；

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

#include <climits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        if (array.empty()) return 0;
        int max_res = INT_MIN;
        int last_sum = 0;
        for(size_t i=0;i<array.size();++i) {
            if(last_sum >=0) {
                last_sum = last_sum + array[i];
            }else {
                last_sum = array[i];
            }
            max_res = std::max(last_sum,max_res);
        }
        return max_res;
    }
};